常用数据结构栈的应用----表达式求值

发表于 | 分类于 | 阅读次数

常用数据结构栈的应用—-表达式求值

栈

栈是常用的数据结构，栈又称堆栈，是一种受限的线性表。其限制是允许在表中的一端进行插入和删除元素。栈中的元素符合后进先出（FILO）的性质。允许插入和删除元素的一端被称为栈顶，另一端被称为栈底。
栈有两种关键的操作，分别为出栈和压栈。

栈有两种关键的操作，分别为出栈和压栈。

  • 出栈(pop)：它是把栈顶的元素E删除，使E的下一个元素称为新的栈顶，并返回元素E
  • 压栈（push）:它是将元素E插入栈顶，使得新插入的元素E称为新的栈顶。

栈的常见的应用主要有：编译器中语法分析的符号匹配、表达式求值、程序的函数调用等。
例如：操作系统中的进程的上下文切换，里面被切换下CPU的进程的现场信息例如寄存器等信息，被保存在堆栈中，等到CPU轮转到该进程时，使用堆栈恢复现场。

表达式求值

表达式求值是栈的一个重要的应用。例如计算器中的加减乘除表达式的计算，都会使用栈来进行求值。
表达式的表示方法主要有中缀表示法和后缀表示法。

  • 中缀表示法：操作符号处于两个操作数的中间例如3+4，中缀表达式是符合人们思维的算术表达式方法，中缀表达式通常包含圆括号和方括号。中缀表达式不容易被计算机所理解，因此不太方便使用其进行表达式求值。

    中缀表示的例子 1 + 3 * （4 + 5）

  • 后缀表达式：不包含括号，运算符号放在两个运算对象的后面，所有的计算按运算符号出现的顺序，严格的从左向右进行运算（不再需要考虑运算符号的优先规则）。

    后缀表达式的例子21+3 对应中缀表达式为（2+1）3

后缀表达式求值

使用后缀表达式进行求值的时候，不需要考虑括号和运算符号的优先规则，只需要从左到右进行计算求值即可。

后缀表达式的求值过程为：

1. 读入操作数，压入栈中直到读取到操作符
2. 如果读取到为操作符，则将栈顶的前两元素出栈，使用该操作符进行运算，得到计算结果
3. 将计算结果压入栈中
4. 重复1、2、3直到表达式末尾

最后栈中只有一个元素，变为最后的计算结果。将其出栈即可。

例如：
中缀表达式（2+1）*3
对应的后缀表达式为21+3*

  • 初始化栈S
  • 读取2和1压入S，此时S为1,2
  • 读取到操作符+,出栈栈顶两元素得到1,2，此时栈为空
  • 使用操作符计算两操作数，得到3（1 + 2 = 3）,将3压入栈S，此时栈S为3
  • 读入3,压入栈S，此时栈为3,3
  • 读取到操作符*,出栈栈顶两元素得到3，3 此时栈S为空
  • 使用操作符*，对两元素进行运算得到9，将9压入栈S
  • 读取到表达式尾部

出栈栈顶元素得到9即为计算结果

计算机通常使用后缀表达式进行表达式求值，但是人们通常输入计算的表达式是中缀表达式，因此在进行表达式求值的时候，应该先将中缀表达式转为后缀表达式，然后使用后缀表达式求出表达式值。后缀表达式求值的过程很简单，已经上面分析过了。现在关键的一步就是中缀表达式转为后缀表达式。

中缀表达式转后缀表达式

中缀表达式转后缀表达式是表达式求值关键的一步，其过程如下：
输入中缀表达式IEXP，
输出后缀表达式SEXP
依次读入中缀表达式IEXP，初始化一个栈S用来存放操作符OP。

1. 如果读取的是操作数，直接输出到SEXP。如果为操作符OP，进入step2，如果为空，证明读取到IEXP尾部，则进入step5
2. 判断OP，若为`(`，无任何输出，直接压栈`(`到S，进入step1；若为`)`，则出栈S的元素输出到SEXP中直到遇见元素`(`，且`(`不输出到SEXP中，然后进入step1；若OP不为`(`和`)`，则执行step3
3. 判断栈S的栈顶元素是否为`(`，若为`（`，则直接将OP压栈到S中；若不为`(`，则将栈S的元素出栈输出到SEXP中，直到栈顶元素的优先级小于OP或者栈空，最后进入step4
4. 将OP压入栈S中，进入step1
5. 将栈所有元素输出到SEXP中

例如
IEXP为（2+1）*3，
初始化一个空栈S.

  1. 读取到操作符(，直接压入栈S，此时栈S为（、。
  2. 读取到操作数2，则直接输出到SEXP，此时S仍为（，SEXP为 2
  3. 读取到操作符号+，由于栈S栈顶元素为(，因此直接将+，压入栈S中，此时SEXP为2，栈S为（、+
  4. 读取到操作数1，直接输出，此时SEXP为21， 栈S为（、+ 。
  5. 读取到操作符)，则出栈S的元素直到碰见(，不输出(和),则SEXP为21+，栈S为空
  6. 读取到操作符号*'压栈到S，此时SEXP仍为21+,栈S为*
  7. 读取到操作数3，直接输出到SEXP中，SEXP为21+3，栈S为*

  8. 读取到文件尾，则出栈S知道栈空，SEXP为21+3*

    最后得到后缀表达式21+3*

    可见，中缀转后缀的关键点在于读取到的操作符为括号的case，栈中的(保留直到遇见操作符)，否则是不会出栈的。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
//int栈
#include <stdio.h>
#include <malloc.h>
#define INCREMENT 20

struct Stack_{
    int* a;
    int capacity;
    int size;
    int top;
};

int pop_(struct Stack_* stack) {
    if(stack->size <= 0 || stack->top < 0)
        return NULL;
    stack->size--;
    return stack->a[stack->top--];
}

void push_(struct Stack_* stack, int c) {
    //扩容
    if(stack->size <= stack->capacity) {
        stack->capacity += INCREMENT;
        int* p = (int*)malloc(sizeof(int) * ( stack->capacity));
        int i;
        int* q;
        q = p;
        for(i = 0; i < stack->size; i++) {
            *(q++) = *(stack->a++);
        }
        stack->a = p;
    }

    //压栈
    stack->size++;
    stack->top++;
    stack->a[stack->top] = c;
}

struct Stack_* initStack_(int capacity) {
    struct Stack_* stack = (struct Stack_*)malloc(sizeof(struct Stack_));
    int* a = (int*)malloc(sizeof(int) * capacity);
    stack->size = 0;
    stack->top = -1;
    stack->a = a;
    return stack;
};

//测试是否字符数组是否存在test字符
int in(char* a, int n, char test) {
    int i = 0;
    for(i; i < n; i++) {
        if(a[i] == test)
            return 1;
    }
    return 0;
}

//优先级比较
int compare(char a, char b) {

    if(a == b)
        return 0;

    if(a == '+') {
        if(b == '*' || b == '(' || b == ')')
            return -1;
    }

    if(a == '*') {
        if(b == '+')
            return +1;
        if(b == '(' || b == ')')
            return -1;
    }
}

//中缀表达式转为后缀表达式
char* infix2Suffix(char* infix, int n) {
    struct Stack* stack = initStack(n);
    char add = '+';
    char mult = '*';
    char left = '(';
    char right = ')';
    char op[4] = {'+', '*', '(', ')'};
    int i = 0;
    char *result = (char*)malloc(sizeof(char) * n);
    char top;
    int j = 0;

    for(i; i < n; i++) {
        char c = infix[i];
        //如果读取的字符不为操纵符，为操作数
        //直接放入输出字符数组中
        if(!in(op, 4, c))
            result[j++] = c;
        else {//开始将操作符压栈
            if(stack->size == 0)
                push(stack, c);
            else {
                //
                if(c != '(' && c != ')') {
                    while(1) {
                        top =  pop(stack);
                        if(top == NULL)
                            break;
                        if(top == '(' || compare(c, top) > 0) {
                            push(stack, top);
                            break;
                        } else if (compare(c, top) <= 0)
                            result[j++] = top;
                    }
                    push(stack, c);
                }

                if(c == '(')
                    push(stack, c);

                if(c == ')') {
                    while(1) {
                        top =  pop(stack);
                        if(top != NULL && top != '(')
                            result[j++] = top;
                        else
                            break;
                    }
                }


            }
        }
    }
    //输出栈中剩余的内容
    while(1) {
        top = pop(stack);
        if(top == NULL)
            break;
        result[j++] = top;
    }
    result[j++] = '#';
    return result;
}

//中缀表达式求值
int evaluate(char* infix, int n) {
    char *suffix = infix2Suffix(infix, n);
    struct Stack_* stack = initStack_(n);
    char op[4] = {'+', '*', '(', ')'};
    int i = 0;
    char opnum1, opnum2;
    char c;

    while((c = suffix[i++]) != '#') {
        if(!in(op, 4, c))
            push_(stack, (int)c - (int)'0');
        else if(in(op, 4, c)){
            int opnum1 = pop_(stack);
            int opnum2 = pop_(stack);
            int tmp;
            if(c == '+')
                tmp = opnum1 + opnum2;
            if(c == '*')
                tmp = opnum1 * opnum2;
            push_(stack, tmp);
        }
    }

    return pop_(stack);
}

int main() {

    char infixExp[13] = {'6', '+', '5', '+', '7',
                        '*', '8', '*', '(', '1',
                        '+', '2', ')'};
    int result = evaluate(infixExp, 13);
    char *suffixExp = infix2Suffix(infixExp, 13);
    printf("\n");
    while(*suffixExp!= '#')
        printf("%c", *suffixExp++);
    printf("\n%d", result);
    return;
}